//
// Created by 朱语 on 2022/9/9.
//
#include <iostream>
#include "tree.h"
#include "vector"
#include "TreeNode.h"
using namespace std;

void flatten(TreeNode* root);

int main(){
    vector<int> pre{1, 2, 3, 4, 5, 6};
    vector<int> in{3, 2, 4, 1, 5, 6};

    tree t;
    t.build(pre, in);

    t.preorderTraversal();

    flatten(t.root);

    t.preorderTraversal();
    cout<<endl;
    t.inorderTraversal();
}

TreeNode* flat(TreeNode** root){
    //空则返回
    if(*root == nullptr)
        return *root;
    TreeNode* ptr = *root;
    //暂存右子树
    TreeNode* backup = (*root)->right;
    //递归处理左子树
    if((*root)->left != nullptr){
        //左子树整理好搬到右子树
        (*root)->right = flat(&((*root)->left));
        //清空左子树
        (*root)->left = nullptr;
        //指针指到右子树最右
        while(ptr->right){
            ptr = ptr->right;
        }
    }
    ptr->right = flat(&(backup));
    return *root;
}

void flatten(TreeNode* root) {
    flat(&root);
}
